/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年03月10日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(0, 0, inorder.size()-1, preorder, inorder );
    }

private:
    TreeNode* build(int prestart, int instart, int inend, vector<int>& preorder, vector<int>& inorder){
        if( prestart > preorder.size() - 1 || instart > inend )
            return NULL;

        TreeNode *root = new TreeNode(preorder[prestart]);
        int index = instart;
        for(index; index <= inend; index++){
           if( inorder[index] == preorder[prestart] )
               break;
        }
        root->left = build(prestart+1, instart, index - 1, preorder, inorder);
        root->right = build(prestart + index - instart + 1, index + 1, inend, preorder, inorder);

        return root;
    }
};
